package date0504;

public class Solution {
	/*
	 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（
	 * 注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
	 */
	public RandomListNode Clone(RandomListNode pHead) {
		if (pHead == null)
			return null;
		RandomListNode node = new RandomListNode(pHead.label);
		node.next = pHead.next;
		node.random = pHead.random;
		node.next = Clone(pHead.next);
		return node;
	}

	/*
	 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点，只能调整树中结点指针的指向。
	 */

	public TreeNode Convert(TreeNode root) {

		if (root == null)
			return null;
		if (root.left == null && root.right == null)
			return root;
		TreeNode left = Convert(root.left);
		TreeNode p = left;
		while (p != null && p.right != null) {
			p = p.right;
		}
		if (left != null) {
			p.right = root;
			root.left = p;
		}
		TreeNode right = Convert(root.right);
		if (right != null) {
			root.right = right;
			right.left = root;
		}

		return left != null ? left : root;
	}

	public static void main(String[] args) {
		Solution solution = new Solution();

	}
}
